To briefly answer some of your more general questions before diving into the weeds:
If it is close enough that my idea would fall under this patent how do
I go about opening dialogue for using parts of the patent in
collaboration with my device.
You'd want to contact the assignee and express interest in taking a license. In this case, that would be Microsoft. You could start here:
http://www.microsoft.com/about/legal/en/us/intellectualproperty/iplicensing/
BUT you should really consult with a lawyer before doing so, in order to make sure you don't wind up getting in over your head (by, say, accidentally providing them with an admission your product would infringe their patent that could later be used against you).
Also, I believe my idea may be different enough, but I am not sure who
I would need to ask to evaluate this claim.
A registered patent attorney or agent is really the only person who can give you a competent opinion on this, but even then there's a certain amount of crystal ball gazing involved. Be suspicious of anyone who gives you black and white/yes and no answers.
As to the specific patent you're concerned about:
The link you provided is to a published patent application. The claims of applications are frequently quite broader than the claims in any patent that ultimately issues, as the applicant generally tries to initially claim a fairly broad scope which is then reduced during the application's prosecution as the examiner finds prior art that reads on the broader claims. In this case, the application issued as a patent, which you can tell by looking here:

If you look at the claims of the patent that actually issued, they're quite a bit narrower.
For example:
Claim 1 of the application you're looking at defines:
A method performed by a computing device, comprising:
receiving a video stream that includes a sequence of video frames;
identifying key frames in the video stream;
binding a hyperlink to an object in the key frames; and
providing a separate stream that includes the hyperlink.
While claim 1 of the actual patent defines:
A method performed by a first computing device having a processor for executing instructions stored in a memory, the method comprising:
receiving a video stream by an authoring tool implemented by the processor on the first computing device, the video stream including a
sequence of multiple consecutive video frames, the video stream being
formatted in a format conforming to a standard video format, wherein
the authoring tool is configured to implement a hyperlink for
association with a specified object visible in the sequence of
multiple consecutive video frames when the sequence of multiple
consecutive video frames in the video stream is displayed on a display
device, the hyperlink to be selectable when the sequence of multiple
consecutive video frames including the specified object is displayed
on the display device;
identifying key frames of the sequence of multiple consecutive video frames in the video stream by the authoring tool implemented by
the processor on the first computing device by identifying a first
frame and a last frame in the sequence of multiple consecutive video
frames in the video stream, the sequence of multiple consecutive video
frames in the video stream including a plurality of intermediate
frames existing between the identified first frame and the identified
last frame;
binding the hyperlink directly to the specified object in each of the key frames by associating a shape to be displayed over the
specified object in the sequence of multiple consecutive video frames
in the video stream when the sequence of multiple consecutive video
frames is displayed on the display device, wherein the hyperlink is
associated with the shape to bind the hyperlink to the specified
object in the sequence of multiple consecutive video frames, wherein
the hyperlink represents a connection between the specified object and
a website accessible via the World Wide Web having information
corresponding to the specified object, wherein the hyperlink is
configured to be activated in an application displaying the video
stream to direct the application to present the website having
information corresponding to the specified object;
providing a separate hyperlink stream that includes the hyperlink and the shape to be displayed in the video stream over the specified
object for transmitting the separate hyperlink stream with the video
stream comprising the with the sequence of multiple consecutive video
frames, wherein the hyperlink stream and the video stream are
transmitted by a communication interface of the first computing device
for transmission over a network using a communication protocol for
receipt by a second computing device,
wherein, when the video stream is displayed by the application at the second computing device, the shape is configured to become visible
over the object in the displayed video stream in response to placement
of a cursor icon of a pointing device onto a video display of the
sequence of multiple consecutive video frames in the video stream
during display of the video stream by the application at the second
computing device; and
receiving feedback information at the first computing device on user behavior regarding the hyperlink associated with the specified
object in the sequence of multiple consecutive video frames in the
video stream, wherein the feedback is received from the second
computing device following display of the sequence of multiple
consecutive video frames in the video stream at the second computing
device, wherein the feedback information includes whether a user at
the second computing device activated the hyperlink associated with
the specified object.
However, you also have to keep in mind that the reason the scope of the application's claims were narrowed is almost certainly because there are other patents that cover that subject matter. If you want to see if any of those patents cover your idea, you'll have to look up this patent's prosecution history, download the rejections the examiner issued during prosecution, and look at the references he cited against the claims.
You can look up the public documents associated with a patent or published application on the Patent Application Information Retrieval (PAIR) website:
http://portal.uspto.gov/external/portal/pair
Once you fill out the CAPTCHA, look up the patent and click on the Image File Wrapper Tab. That will give you a list of all the documents you can look at with respect to this particular patent:

Hope that was enough information to get you started.
Good luck.