Config Test Deployment for VS2010

The MSDN document How to: Config Test Deployment is somewhat out-dated. .testrunconfig in VS2010 is actually local.testsettings. Another config file 'TraceAndTestImpact.testsettings' really fooled me. ^_^

Mean-shift Object Tracking Study Notes

Xueqing Sun

sunshaking@gmail.com

June 12^th, 2011

License CC BY

You can distribute, remix, tweak, and build upon this work, even commercially, as long as you credit Xueqing Sun for the original creation.

I was reading a book, ‘Image Processing, Analysis, and Machine Vision, Milan Sonka, Vaclav Hlavac, Roger Boyle’ for studying mean-shift object tracking algorithm. But the book was really hard to understand, especially for a beginner of machine vision. Yesterday, with the help of Guangwei, a friend of mine (he is a scientist at National Astronomical Observatories, Chinese Academy of Science), I finally understood the algorithm. And I would like to explain what I understood for sake of helping other guys who are still struggling on this algorithm.

Heads up Questions

1. What is the probability density function of an image?

2. How does the density function contribute to target model?

3. What’s kernel function? How does it work?

 

Here is the summary of the algorithm

To locate a target on an image, we must have a target model, an image which contains the target. The goal of mean-shift algorithm is to tell you the position of your target on the image. Suppose we have a target model image with 5*5 pixels. The pixel values listed below:

x	y	pixel
0	0	1
0	1	1
0	2	6
0	3	5
0	4	7
1	0	0
1	1	4
1	2	7
1	3	0
1	4	4
2	0	3
2	1	5
2	2	7
2	3	1
2	4	5
3	0	7
3	1	0
3	2	9
3	3	9
3	4	2
4	0	0
4	1	1
4	2	4
4	3	3
4	4	3

Target model image

The row x and y are the location of a pixel on the image. And the third row ‘pixel’ is the value. For convenient purpose, we limit pixel value from 0 to 9. Now we can create a frequency table like below. Normally images are colored, but we simplified the problem from colored images to gray scale images. A colored image can be considered as a composition of three gray scale images. So the rationale explained here can be easily applied to colored images.

bin	q
1	8
2	1
3	3
4	3
5	3
6	1
7	4
8	0
9	2

Frequency

The frequency means how many pixels located in a specific bin. For example, the first row means there are 8 pixels which values are less or equal to ‘1’. Furthermore we can have histogram chart for the table.

Histogram

On the book, and many other materials, the density function of target model, defined as below:

1

The density function is closely related with the frequency table. Here the black is a vector which has m components. In this case, the m is 9 because we have 9 bins. Each component is made from corresponding bin. Let look into the component definition.

2

The definition looks somewhat complex. Let’s split it into parts so we can understand it easier. First, let’s see the delta part

3

n is the pixel number. In this case we have 25 pixels. So the n is 25. is the coordinate of i^th pixel in the image. For example, the first pixel coordinate is (0,0), and the second is (0,1). u means we are currently defining u^th component corresponding to u^th bin. Function tells which bin the pixel go. For example, the first pixel (0,0) is 1, so it goes to bin 1, i.e. .

Actually, the formula 3 is a vector, let’s rewrite it as following:

4

The delta function gives you 1 if the pixel goes to bin u, otherwise it gives 0. So this vector works just like a mask. On the mask there are ‘1’s mark the pixels go to bin u. For example, if our image is 4*4, we might get a D vector like this:

1	0	0	1
0	1	1	0
0	0	0	1
1	0	0	0

The image is a matrix. D is a vector. Just put each row of the matrix to one row in sequence then we’ll get D.

IMPORTANT

What’s the relationship between D and the frequency table? The answer is for each u, . Actually we can form feature space only based on D, because D already represents the image in statistics way. So mean-shift algorithm is so called an algorithm that based on probability density function. But marginal pixels are unstable, so the kernel function which is a weight function does the work. It give marginal pixels less weight to make the objective function in optimization process more stable.

 

OK, let’s see another part of formula 2. It’s

5

Again it’s a vector. Function k is the kernel function which actually is a weight function giving each pixel position a weight. So can be defined as below:

6

It looks beautiful. I really hate which makes formula unreadable.

OK, now we get the density function of target model image. The candidate density function is pretty similar.

	7
	8

Formula 8 is easier to understand because we’ve already understood formula 2. The k function in formula 8 is just a transformed version of original k.

I think I’ve solved the hardest part of the mean-shift algorithm. And the rest of it would be much easier to understand because it is just kind of an optimism algorithm to find the y.

High Resolution Timer via Interop

Though Windows isn’t a real-time OS, we do need high resolution clocks and timers sometimes. .Net gives us Stopwatch class which is really a high resolution clock. But we can’t find a high resolution timer in .Net framework. A timer is different from a clock, which fires event periodically notifying you the period of time is up. This article is mainly to demonstrate the basic usage of interop. And a more complex and intensive material provided at the end of the article.

There are high resolution timer services on Windows. But they are native APIs. Fortunately, we can use interop to call these native APIs.

The first thing you have to do is to determine the device capabilities. Different devices have different resolutions[1]. Some may give you 1 ms of resolution, but some may be 10 ms. And if you request a resolution that the device can’t support, an error will occur. To determine the resolution of the timer hardware, use timeGetTime().

[DllImport("winmm.dll")]
private static extern int timeGetDevCaps(ref TimerCaps caps, int sizeOfTimerCaps);

TimerCaps is a struct. A C struct actually. We can use C# struct to map the data.

[StructLayout(LayoutKind.Sequential)]
public struct TimerCaps
{
    /// <summary>
    /// Minimum supported period in milliseconds.
    /// </summary>
    public uint periodMin;
    /// <summary>
    /// Maximum supported period in milliseconds.
    /// </summary>
    public uint periodMax;
}

Please keep in mind that “LayoutKind.Sequential” is essential, because it suppressed C# compiler from alter the order of the fields for optimization purpose. Here for the parameter “TimerCaps caps” we use “ref”, because we want the API to write some data into “caps”. The “ref” maps the type to the pointer of the type in C/C++. So “ref TimerCaps caps” means “TimerCaps *caps” in C/C++.

Now we can call the API.

TimerCaps caps = new TimerCaps();
int ret = timeGetDevCaps(ref caps, Marshal.SizeOf(caps));

And then we can start the timer.

[DllImport("winmm.dll")]
private static extern int timeSetEvent(uint delay, uint resolution, MmTimerCallback proc, int user, int mode);
...
actuallPeriod = Math.Max(caps.periodMin, Period);
timeBeginPeriod(actuallPeriod);
timerId = timeSetEvent(1000/*delay*/, 0/*resolution*/, TimerCallback, 0, 1);

“MmTimerCallback” is a delegate method mapping to callback function in C/C++. That’s almost the complete stuffs of the high resolution timer. Please be aware, the callback function will be called in a thread other than your main thread. You have to delegate the operation to your main thread if you want to access UI elements.

Here is a good read material talks about interop.

• Calling Win32 DLLs in C# with P/Invoke - Jason Clark

The Way of Quitting an Application

There are several ways of letting an application to quit programmatically. But you should choose the best one among them.

Environment.Exit Method

This method will force a process to terminate. So the process has no chance to do cleaning up work. No code after Environment.Exit will be executed. Any data that is unsaved will be lost. Not recommend this way.

Process.Kill Method

Killing a process just like Environment.Exit, terminates the process immediately and the process doesn't have the last chance to breath. So again, it's not recommended.

Process.CloseMainWindow Method

This method will send a request to a process' message loop, if the process does have a message loop. The process thus has a chance to do cleaning up work, and save unsaved data to disk then terminates gracefully. This method can be called either from another process or within the process that to be terminated.

Environment.Exit Method http://msdn.microsoft.com/en-us/library/system.environment.exit.aspx

Process.CloseMainWindow Method http://msdn.microsoft.com/en-us/library/system.diagnostics.process.closemainwindow.aspx

Tricks for repairing Visual Studio if it doesn't work with unit test

Sometimes, Visual Studio doesn't work with unit test. Unit test list can't be loaded when you try to load an old unit test project. Or, it can load the list, but when you try to run the unit test case, Visual Studio just tell you it is not able to run the unit test, blah blah blah...

There must be bugs in Visual Studio or in your unit project settings. Please try the following, the easiest one first:

1. Delete .suo, .vsmdi of your solution then reload your project.
2. Type devenv /setup or devenv /resetuserdata. But please be careful, it will clear your user setting data and Visual Studio will start from a factory state.
3. Check if any references of your unit test project does not work. Just click on the reference, if Visual Studio will bring you to the correct position of the Object Browser, it's the correct reference. Otherwise, not. To fix the reference, first remove the reference, then add it again. If you can't find the reference, probably you have to reinstall the relevant software. The issue I met is TeamSystem.Data.UnitTesting won't work. And the attribute TestMethod is undefined because it is defined in the assembly that hasn't been referenced correctly from the unit test project.

Tricks for Writing Unit Tests for WPF Applications

Usually you write unit tests for non-UI related classes that only do background logics. But sometimes you can't avoid writing unit tests for UI related classes. These days I tried such kind of unit test. And there are some tricks that are useful while you are writing WPF unit tests I willing to share with you. Let's get started.

Get Your Window Ran

First thing first, you should get your window shown and ran. If your window is a child window of your whole application, then you have to create a fake parent window. And then build relationship between the testee window and the fake parent window.

Window fakeParentWindow = new Window();
Foo testee = new Foo();
fakeParentWindow.Content = testee; // if testee is a kind of UIElement
testee.Owner = fakeParentWindow; // if testee is a kind of Window
fakeParentWindow.Show();
testee.Show(); // if it's a Window

If the testee is a Window, you can let it be the child window of the fakeParentWindow by assign fakeParentWindow to testee's property Owner. Or just do nothing you will get a top window testee. Don't forget to call Show() if it is a Window.

That's not everything of initializing a stage for your unit test. There are at least two threads you may interested in

• Main thread
  
• The worker thread running as an agent for your unit test case (I don't know why it is called an agent thread)
  

As listed above, your test case will be running within a worker thread. Almost all thread time are dedicated to your test method if you don't carry out some special actions. If your test method blocks the worker thread, your windows won't get message pumped and events won't be handled, and windows even won't get rendered. To solve the problem, just call System.Windows.Threading.Dispatcher.Run() which will start pumping messages and get dispatcher works.

Dispatcher.CurrentDispatcher.BeginInvoke(
DispatcherPriority.Background,
new DispatcherOperationCallback(CarryOutTestSteps),
null);

System.Windows.Threading.Dispatcher.Run();

Since Dispatcher.Run() will block the test method, you have to invoke your test steps via CurrentDispatcher.BeginInvoke() in order to starting test. Your test steps will still be processed in the worker thread, but it will be processed as a dispatcher work item.

By now, your window is showing.

Don't put Dispatcher.Run() into TestInitialize(), because Dispatcher.Run() will also blocks the thread and your test method won't get the chance to run.

Quit the Unit Test

Soon you will find that the unit test won't quit even the dispatcher work item has been completed, and even you close the windows manually. The thread is still enjoying pumping messages. To tell it to stop doing stupid things, just call Dispatcher.ExitAllFrames() when you finished all test steps:

System.Windows.Threading.Dispatcher.ExitAllFrames();

Everything looks good, but... you will get an exception during the thread's termination. The exception says:

"An unhandled exception of type 'System.Runtime.InteropServices.InvalidComObjectException' occurred in PresentationCore.dll Additional information: COM object that has been separated from its underlying RCW cannot be used."

I searched on the Internet. Eventually I found that was a bug of .Net Framework. A work around came from Visual Studio Product Team is calling CurrentDispatcher.InvokeShutdown() from TestCleanup().

[TestCleanup]
public void TestCleanup()
{
System.Windows.Threading.Dispatcher.CurrentDispatcher.InvokeShutdown();
}

Be careful, .Net Framework may be changed letting this work around unnecessary.

References

1. WPF / Visual Studio 2008 Unit Test Workaround
   
2. Unit Tests Which Show Windows Cause VsTestHost/MsTest ShutDown Crashes in VS 2008 RTM
   

WPF Threading Model via Windbg

In this post, I will show you how to discover the threading model of WPF via Windbg. This post is not a complete description of WPF threading model, but just listed what I've found after my efforts.

Windbg is a powerful debugger, though may be not the most powerful one. It can really help you to find root causes for some though bugs. Download Windbg here.

To dive into WPF, first, create a simple WPF application. Just use Visual Studio to create a default WPF application project. And build the application to get executable generated. Then, launch Windbg, and load it into Windbg. Don't forget to load Windbg extensions such as sos or psscor2, to help your debugging.

OK, let the application run. When you see the application window, break the application by clicking the 'break' button on the Windbg's toolbar. Let's go to thread 0 and see its stack by these two commands:

~0s
!clrstack

The first command switches current thread to 0, and the second will display CLR stack. It's very clear that thread 0 is our UI thread.

0030e824 56d5dfe0 MS.Win32.HwndSubclass.SubclassWndProc(IntPtr, Int32, IntPtr, IntPtr)
0030ec5c 00a20bd3 [InlinedCallFrame: 0030ec5c] MS.Win32.UnsafeNativeMethods.CallWindowProc(IntPtr, IntPtr, Int32, IntPtr, IntPtr)
0030ec58 56d5f0fe MS.Win32.HwndSubclass.DefWndProcWrapper(IntPtr, Int32, IntPtr, IntPtr)
0030ede8 00a20bd3 [NDirectMethodFrameStandalone: 0030ede8] MS.Win32.UnsafeNativeMethods.CallWindowProc(IntPtr, IntPtr, Int32, IntPtr, IntPtr)
0030ee04 56d5dfe0 MS.Win32.HwndSubclass.SubclassWndProc(IntPtr, Int32, IntPtr, IntPtr)
0030ef90 00a20bd3 [NDirectMethodFrameStandalone: 0030ef90] MS.Win32.UnsafeNativeMethods.DispatchMessage(System.Windows.Interop.MSG ByRef)
0030efa0 56d61824 System.Windows.Threading.Dispatcher.PushFrameImpl(System.Windows.Threading.DispatcherFrame)
0030eff0 56d616c7 System.Windows.Threading.Dispatcher.PushFrame(System.Windows.Threading.DispatcherFrame)
0030f00c 56d6162d System.Windows.Threading.Dispatcher.Run()
0030f018 5533ddb0 System.Windows.Application.RunInternal(System.Windows.Window)
0030f044 5533dbe5 System.Windows.Application.Run(System.Windows.Window)
0030f054 5533d836 System.Windows.Application.Run()
0030f05c 003500ad SimpleWPFApp.App.Main()
0030f284 79e7c74b [GCFrame: 0030f284] 

You may want to try other threads, and will find they are not CLR threads. And next step, let's try to find which thread is render thread. Use command 'kb' repeatedly and you will find one thread looks interesting. It is trying to GetWork and is waiting for something.

0:005> kb
ChildEBP RetAddr  Args to Child              
0491fab0 77719254 7679c244 00000234 00000000 ntdll!KiFastSystemCallRet [d:\rtm\base\ntos\rtl\i386\userdisp.asm @ 645]
0491fab4 7679c244 00000234 00000000 00000000 ntdll!ZwWaitForSingleObject+0xc [o:\rtm.obj.x86fre\base\ntdll\daytona\objfre\i386\usrstubs.asm @ 2939]
0491fb24 7679c1b2 00000234 ffffffff 00000000 KERNEL32!WaitForSingleObjectEx+0xbe [d:\rtm\base\win32\client\synch.c @ 1524]
0491fb38 72790b19 00000234 ffffffff 004dd410 KERNEL32!WaitForSingleObject+0x12 [d:\rtm\base\win32\client\synch.c @ 1429]
0491fb68 7278aadc 0491fb7c 004dd410 004dd4a0 MilCore!CPartitionManager::GetWork+0x1a5 [d:\rtm\windows\mil\core\uce\partitionmanager.cpp @ 1111]
0491fb80 7278aaa4 00000000 00000000 004dd410 MilCore!CPartitionThread::Run+0x1a [d:\rtm\windows\mil\core\uce\partitionthread.cpp @ 222]
0491fb98 76794911 004dd410 0491fbe4 776fe4b6 MilCore!CPartitionThread::ThreadMain+0x1e [d:\rtm\windows\mil\core\uce\partitionthread.cpp @ 46]
0491fba4 776fe4b6 004dd410 73edafdb 00000000 KERNEL32!BaseThreadInitThunk+0xe [d:\rtm\base\win32\client\thread.c @ 66]
0491fbe4 776fe489 7278aa86 004dd410 00000000 ntdll!__RtlUserThreadStart+0x23 [d:\rtm\base\ntos\rtl\rtlexec.c @ 2740]
0491fbfc 00000000 7278aa86 004dd410 00000000 ntdll!_RtlUserThreadStart+0x1b [d:\rtm\base\ntos\rtl\rtlexec.c @ 2672]

By checking the call stack, we find there's an argument passed to WaitForSingleObject and WaitForSingleObjectEx. The argument is 00000234. It looks like some synchronization objects. Let's check what is it:

0:000> !handle 0x234 ff
Handle 234
  Type             Event
  Attributes       0
  GrantedAccess    0x1f0003:
         Delete,ReadControl,WriteDac,WriteOwner,Synch
         QueryState,ModifyState
  HandleCount      2
  PointerCount     4
  Name             <none>
  Object Specific Information
    Event Type Auto Reset
    Event is Waiting

Windbg tells us it's an event handle. Hmmm, that's reasonable. If you continue to check other thread's call stack, and you will find there's only one thread is waiting for some synchronization events. This thread must be render thread, because communication between render thread and UI thread must be based on synchronization object. So, next task is to find where the event been set. Set breakpoint on KERNEL32!SetEvent won't work for us because there are so many calls to SetEvent everywhere in the application. Windbg offers a kind of conditional breakpoint which can help us to break the application at the right position.

bp kernel32!SetEvent "j (edx=234) '.echo foo';'gc'"

Here 234 is the event handle, remember that we found this handle in render thread. You should replace it with the handle you find in your situation. Let the application go. The breakpoint is so great though, it seems that it can't be hit every time when the code goes to the right position. I don't know why. But if you try to resize the application's window repeatedly, you will have greater chance to hit the breakpoint. When the application got hit the breakpoint, you can see the call stack of thread 0 like this:

0:000> kb
ChildEBP RetAddr  Args to Child              
0030d95c 72748a36 00000234 004de51c 004b3a18 KERNEL32!SetEvent+0x14 [d:\rtm\base\win32\client\synch.c @ 506]
0030d978 727489d1 004b3a18 004de2f0 00000000 MilCore!CPartitionManager::ScheduleBatchProcessing+0x54 [d:\rtm\windows\mil\core\uce\partitionmanager.cpp @ 482]
0030d9d0 7274974e 0030d9ec 0030da24 004e7188 MilCore!CComposition::SubmitBatch+0x96 [d:\rtm\windows\mil\core\uce\composition.cpp @ 359]
0030d9e4 727488ba 004b3a18 0030da34 004de1d0 MilCore!CConnectionContext::SendBatchToChannel+0x30 [d:\rtm\windows\mil\core\uce\connectioncontext.cpp @ 568]
0030d9f8 72748868 00000004 004e7294 0030da3c MilCore!CConnectionContext::SendPacketToConnection+0xee [d:\rtm\windows\mil\core\uce\connectioncontext.cpp @ 450]
0030da08 727491cd 0030da24 01d47b28 00000003 MilCore!CMilCrossThreadTransport::PostPacket+0x3b [d:\rtm\windows\mil\core\uce\crossthreadtransport.cpp @ 145]
0030da3c 727491ff 004e7294 004e7208 72742c35 MilCore!CMilConnection::SubmitBatch+0xa9 [d:\rtm\windows\mil\core\uce\connection.cpp @ 619]
0030da48 72742c35 01d47b28 72742c9f 004e7208 MilCore!CMilChannel::FlushCommands+0x21 [d:\rtm\windows\mil\core\uce\clientchannel.cpp @ 721]
0030da50 72742c9f 004e7208 0030daa0 5395bc2d MilCore!CMilChannel::Commit+0x20 [d:\rtm\windows\mil\core\uce\clientchannel.cpp @ 626]
0030da5c 5395bc2d 004e7208 a1590ca7 79e73940 MilCore!MilChannel_CommitChannel+0x21 [d:\rtm\windows\mil\core\uce\apifunc.cpp @ 523]
0030daa0 539bb1b3 0000004f 00000003 00000000 PresentationCore_ni!`dynamic atexit destructor for '<CrtImplementationDetails>::AtExitLock::_lock'' <PERF> (PresentationCore_ni+0xbbc2d)
0030db10 53977fea 00000000 0000020f 0000024e PresentationCore_ni!`dynamic atexit destructor for '<CrtImplementationDetails>::AtExitLock::_lock'' <PERF> (PresentationCore_ni+0x11b1b3)
0030db98 79e75519 56d61428 00000000 01d116b0 PresentationCore_ni!`dynamic atexit destructor for '<CrtImplementationDetails>::AtExitLock::_lock'' <PERF> (PresentationCore_ni+0xd7fea)
0030db9c 56d61428 00000000 01d116b0 01d6c134 mscorwks!ThreadNative::FastGetCurrentThread+0x6 [f:\redbits\ndp\clr\src\vm\comsynchronizable.cpp @ 1004]
00000000 00000000 00000000 00000000 00000000 WindowsBase_ni!IsEncryptedPackageEnvelope+0x53 [d:\SP1\windows\wcp\Base\System\IO\Packaging\EncryptedPackage.cs @ 595]

It's interesting. Isn't it? Check the handle 234 right now and you will see the event is still in waiting state. But if you step over KERNEL32!SetEvent, you will find the event turned to 'set state':

0:000> !handle 0x234 ff
Handle 234
  Type             Event
  Attributes       0
  GrantedAccess    0x1f0003:
         Delete,ReadControl,WriteDac,WriteOwner,Synch
         QueryState,ModifyState
  HandleCount      2
  PointerCount     4
  Name             <none>
  Object Specific Information
    Event Type Auto Reset
    Event is Set

From current UI thread's call stack you can find the data submission and synchronization secrete. UI thread and render thread are working in an asynchronous mode. It means that even if you completed some invocations of drawing objects, these drawing commands may be pending in the queue and won't be executed by render thread. I remember that once I am developing a program that drawing some animation, I found that even if I received the animation completion event, the animation was still going on on the screen.