Topic: vgstitch

[DarkWolf]

I sat down last night and ported my PHP stitching script to C.  I think I got things as fast as they are going to get.  I still have some things to finish before I release it.  It did a Kishi Densetsu map in about 23 seconds, the first level of Mario goes in about 11.  I also did some isometric samples, like SimCity 2000 and Light Crusader.  Those take more like 4-6 minutes.



Just a heads up, this isn't the same thing as Maxim's program.  This one is for human-taken screenshots with overlap.  Each consecutive map has to overlap one of the previous images, but it doesn't have to go in any particular direction.  There's no threshold, other than a masking (or neutral) color, so animation / sprites will have to be masked out.



Kishi Densetsu sample:

[Maxim]

Just out of interest in the algorithm... my guess is:



- for each possible overlap of images

-- see if all non-set pixels in the map match the screenshot

-- if so, count how many pixels matched

- choose the one that matched the most pixels



There's a few reasons why I didn't go with that:



1. As the map gets bigger, the number of possible overlap positions gets extremely large (although at least it's proportional to the map area rather than any higher power)

2. It can't handle extremely repetitive images, eg. a screen full of the same repeating block

3. It can't handle sprites, or background animation, or parallax, at all

4. I was writing it in Delphi which isn't super-fast, and I liked making it have a GUI and be watchable even if that slows it by a fraction

5. I was working on the principle of having high-frame-rate screengrabs as the source data the whole time



Possible caveats to these:



- You could use some smoothing/subsampling to rapidly find suitable stitch locations, somewhat like the way photo stitching works, but that sounds quite tricky

- You could refuse to stitch images in places where all the pixels are known, to reduce the search space

- If #3 is acceptable, the "discard location" threshold is just 1 non-matching pixel, which is much faster than mine



The sample looks really good. Can you say how many source images it took?



I found that implementing a mask image (applied to input images, to get rid of the player sprite/status bars/etc) made a surprisingly big difference. I recommend you try it.

[DarkWolf]

Yeah you pretty much figured out the algorithm.  And you are right on the downsides.  One way I was able to overcome the larger number of possibilities was to exclude any match where each of the four corners was the masking color.  This means large images won't engulf small ones and peninsular matches won't work.  The mapper will have to take "good" screenshots for the tool to work well (or at all).  Obviously it isn't going to work well for every application.



The sample was comprised of about 20 images.  I wanted to include it with the release, but I was worried about sticking copyright material with the program.  I can upload the individual images separately if anybody has an interest.



vgstitch version 1

[Maxim]

The sample is 1576x632, if we assume source images of 320x224 then it's using an average overlap of 31% between images. I'd say that's on the high side for human-targeted screenshots but certainly a lot less than my program - I usually work with >90% overlap.

[Maxim]

I tried to use it for the first time and it's crashing with a null pointer exception whenever I run it.

[DarkWolf]

Does this happen even when the program is run without parameters?  I've run it several times on my machine without incident.  I don't have any processor specific options enabled either.  I'll try it on some of my other machines when I get a chance.

[Maxim]

When run without parameters it shows the usage info. When I pass a directory name it crashes with the NPE. There's no DLL dependency issues showing up.



If you like, and it's not hard to compile, send me the sources and I'll debug into it.

[The Ultimate Koopa]

As usual I'm being an idiot, but how exactly do you use this? Do you copy all the images you want to 'stitch' in the same directory as vgstitch, and simply double-click on vgstitch? Do you have to do something else? Do you have to use cmd.exe or something? When ever I try to use the most common method of opening a program (double clicking), it just flashes.

[Maxim]

You need to use a command prompt.



DarkWolf:



C:\vgstitch>vgstitch.exe

Usage: vgstitch.exe (OPTIONS) Directory



C:\vgstitch>vgstitch.exe foo



C:\vgstitch>vgstitch.exe

Usage: vgstitch.exe (OPTIONS) Directory



C:\vgstitch>vgstitch.exe foo

Cannot read directory foo



C:\vgstitch>md foo



C:\vgstitch>copy *.png foo

map001.PNG

map002.PNG

map003.PNG

map004.PNG

map005.PNG

        5 file(s) copied.



C:\vgstitch>vgstitch.exe foo



An unhandled win32 exception occurred in vgstitch.exe[52968]. [...] Do you want to debug using the selected debugger?



foo.png is created, 0 bytes; the debugger suggests the crash point is rather deep inside bgd.dll.

[DarkWolf]

I didn't find the source of the problem last night, but I did find some logic errors that need fixing in the main function, so at least that was good.



I tried it on four machines, two at home, two at work.  Haven't been able to recreate the error.  I can send you the Dev-C++ project when I get home.

[DarkWolf]

Version 1.1



This fixes some logical errors and adds a new command line option.  Not sure if it fixes Maxim's problem.

[Maxim]

That fixed it. The problem: my images had uppercase .PNG extensions. It now reports

"No valid image files found in <directory>"

which is better than crashing, and after a rename all is well.