Feeds:
文章
评论

Archive for 2007年8月

From 2007.08.11 So…

事实证明,写日记是要花很多时间。全力以赴的工作的话,是没有时间写一篇日记的。由此推理:以前写那么多日记的时候,都没有好好工作……无论如何,现在不记下一些东西,以后要忘记,要后悔的。

自从云震不再一天躺上20个小时任人摆布,自从云震逐渐通过眼神、声音和动作响应外界,甚至准确的完成认画片、取玩具、垒积木等动作,我们一次一次的惊呼和赞叹小河马长大了、小河马懂事了。

长大了,懂事了,“翅膀要硬了”,有自己的愿望和要求了。

逐渐的,爸爸和妈妈开始讨论小河马听话不听话的话题了。

云震的“愿望”和“要求”很简单。例如看到喝奶用的大瓶瓶、看到桌子上放的水果或姥姥精心烹制的晚餐、看到柜子上的玩具汽车。这些显然归结为吃和玩。

“愿望”和“要求”是要被满足的。哭是小河马表达不满的利器,好在就目前,这也是小河马表达不高兴的唯一办法。

刚刚学会走路的小河马,很享受满屋子乱转,晃着走来走去。摔跟头自然正常,磕磕碰碰也难以避免,因为云震总是忙着到屋子各个犄角旮旯“探险”。

磕疼了,会哭的。但这哭就有了区别了。

如果当着姥姥的面(姥姥通常都跟在小河马后面,弓着腰张着手护着小河马往前走,怕云震走不稳倒了,即使如此,也难免磕碰的时候),就要卖力的哭上一次,咧开嘴,眼泪哗哗的。非要姥姥一把搂到怀里抱上了,才止住哭声。赖在姥姥怀里还要回身指着刚才跌倒的地方愤愤地哼唧几下,一副找到了靠山要下次再来的劲头。

如果姥姥刚好不在,是爸爸在,情况会不一样。在一个房间里,爸爸不跟着小河马走。小河马自己溜达,爸爸坐在地上或者沙发上看着。爸爸仔细观察过,例如云震摔到在床边,如果只是摔倒了,没磕没碰,自己吓到自己而已,小河马不会立刻哭,而是先委屈着撇嘴,并且立刻回头看大人这边。看到是爸爸,而且爸爸还“无动于衷”,一点立刻过来扶起来的意思都没有,哭就没法发作了。这时候,小河马会一边哼唧一边懊恼的爬起来,悻悻的绕开摔倒的地方,继续晃悠着“探险”。

为了“锻炼”小河马,即使姥姥在场,妈妈和爸爸往往先拦一下姥姥,让小河马自己先缓上一会看看情况。

不过也有真摔到的时候,前几天甚至把鼻子都摔出鼻血了。那可就不管不顾的真哭开,很悲恸的。

另外有个很有意思的事情。

大屋里面有一个电暖气,小河马刚来的时候,虽然是5月了,但天气还是冷,那时候还开着暖气。

还刚刚会爬的小河马很好奇的够那个暖气,不幸被烫到手,大哭过后,被妈妈教育这个东西烫,不能摸。之后,每次小河马爬到电暖气跟前,都要认真的盯上一会,然后看看大人自己摆摆手,意思是“这个烫,云震不摸”。

这个摆手的动作很可爱。

云震逐渐在家里拓展之后,越来越多的地方被大人“声明”为云震不能摸不能去的地方。然而这些声明是阻止不了云震的,小河马还是要亲自到此一游,但很小心的回头看看大人,先摆摆手。如果大人赞同的表示“对了,这地方不能摸”,小河马就止步于前,不越雷池一步;如果大人这个时候不置可否,小河马就会壮上胆子继续“拓展”。

有意思地方在于,有的时候,云震已经抬头看过大人了,下意识的摆摆手表示“这地方我不动”了,但不等大人置可否,立刻展开行动,该跑的跑,该抓的抓,那是诱惑实在太大的时候呢。

鉴于云震这个“征求大人意见”的良好表现,爸爸、妈妈和姥姥一致认为云震还是听话的小孩。

Technorati 标记: , , ,

Read Full Post »

— C#, eBay API, web programming, multi-thread programming, XML document programming and etc

[Codeproject link]

Project CorgiPrice has very specific function: retrieving the prices, in addition to the other eBay trading information, of Corgi die-cast models listed on eBay, and getting the corresponding reference prices from the other online shops, in order to assist bidding (for Suyan, my wife, and my little one).

However, developing tiny CorgiPrice involves various C# programming topics, such as web programming (to use eBay API), XML document programming, multi-thread programming and etc. At the end of the day, I found it worth dozens of hours to make wife happy. Also, I feel it worth another couple of hours to share these basic C# programming topics.

Introduction

Suyan, my wife, fancies Corgi die-cast models. She bids on eBay as there are sometime very rare models on the lists and fairly good offers as well. Housewives would feel more productive should they have convinced themselves that they have had really good offer, for an instance, their bidding prices are reasonably lower than the market on-the-table prices. The latter usually comes from cross-referencing the other online shops. Moreover, once there is a long watching list, and the items on the list come to the end very closely in turn, an automatically "cross-referencing" batch work seems very essential for serious bidders, such as my wife.

Project CorgiPrice was request by my wife, who could not wait for bidding a list of hundreds of models from a serious eBay Corgi seller. So, CorgiPrice should be capable to retrieve information of items on the list from eBay, including the current bidding price, bid counts, ending time and etc. Moreover, CorgiPrice must also automatically search a reference price from another online shop. These tasks require C# web programming (to use eBay API) and XML document programming. In addition, to do a batch work, reference prices are obtained item-wise by a multi-thread programming. The user interface uses a ListView control to display item information in details.

This article is arranged as following: first, eBay API is illustrated. Techniques involved to use eBay API are studied in section Web Programming and XML Document Programming in turn, in addition to the source code snippets of searching the reference price from the other online shops. Multi-thread Programming deals with basic and safe multi-thread programming topics. The last section concludes the article and points out possible future works, to extend CorgiPrice to meet more requests. Source codes and a demo project are included.

eBay API

eBay API [1] is a set of website interfaces providing functions of obtaining/sending bidding items information from/to eBay. There are two main groups of eBay API, Shopping Web Services and Trading Web Services. Shopping Web Services provides only downstream functions, while Trading Web Services allows the third-party programs to list selling items to eBay as well.

To develop a C# desktop program, it is convenient to use HTTP POST protocol and XML input/output formats to implement eBay web services to retrieve items information from eBay. (The other options are available on eBay developers program website [1] as there is an eBay SDK for .Net and tons of tutorials and sample codes [2] for Windows programming.)

To use HTTP POST, it requires a set of eBay development keys (register to eBay developers program). The keys include DevID, AppID, CertID, and Auth Token (should you also have an eBay account). Refer to eBay quick start guide [3] to register to eBay developers program and obtain your own development keys.

eBay API is a set of website interfaces, i.e., call methods. Providing a call method, such as GetSearchResults, we need fill in input fields (request) and output fields (response). CorgiPrice uses XML formats to send/receive information to/ from eBay API servers.

Details of using eBay API are explained in the following two sections.

Web Programming

CorgiPrice uses System.Net assembly to make a call to GetSearchResults of eBay Trading Web Service, using Production (not sandbox) environment.

HttpWebRequest object is used to establish a web connection to eBay API servers. The HTTP HEADER parameters include eBay development keys, API versions, call method name, and the site international ID.

[Source Code Snippet, part of ConnectTradingWebService()]

#region connection parameters
string productionDevID = "YOURDEVID";
string productionAppID = "YOURAPPID";
string productionCertID = "YOURCERTID";
string productionTradingWebServiceServerUrl = "https://api.ebay.com/ws/api.dll";
//SiteID, US = 0, UK = 3, Canada = 2, Australia = 15, ....
//SiteID Indicates the eBay site to associate the call with
int siteID = 3;
#endregion
#region setup HttpWebRequest (inc. HTTP Headers)
//Create a new HttpWebRequest object for the ServerUrl
HttpWebRequest request = (HttpWebRequest)WebRequest.Create(productionTradingWebServiceServerUrl);
//Set Request Method (POST) and Content Type (text/xml)
request.Method = "POST";
request.ContentType = "text/xml";
//Add the Keys to the HTTP Headers
request.Headers.Add("X-EBAY-API-DEV-NAME: " + productionDevID);
request.Headers.Add("X-EBAY-API-APP-NAME: " + productionAppID);
request.Headers.Add("X-EBAY-API-CERT-NAME: " + productionCertID);
//Add Compatability Level to HTTP Headers
//Regulates versioning of the XML interface for the API
request.Headers.Add("X-EBAY-API-COMPATIBILITY-LEVEL: 433");
//Add function name, SiteID and Detail Level to HTTP Headers
request.Headers.Add("X-EBAY-API-CALL-NAME: " + callMethod);
request.Headers.Add("X-EBAY-API-SITEID: " + siteID.ToString());
//Time out = 15 seconds,  set to -1 for no timeout.
//If times-out - throws a WebException with the
//Status property set to WebExceptionStatus.Timeout.
request.Timeout = 15000;
#endregion

After inserting input fields (see the next Section) into the HttpWebRequest object, CorgiPrice communicates with eBay API servers by sending the request and retrieving the response (a WebResponse object), and then converts the output fields (of response) into XML format. Item details are parsed by analysing the output XML document.

[Source Code Snippets, part of GetUserListByTradingWebService()]

Stream stream = null;
try
{
    //Set the request Stream
    stream = request.GetRequestStream();
    //Write the equest to the Request Steam
    stream.Write(utf8Bytes, 0, utf8Bytes.Length);
    stream.Close();
    //Get response into stream
    WebResponse resp = request.GetResponse();
    stream = resp.GetResponseStream();
}

HttpWebRequest and WebResponse objects are also used to search a reference price from another online shop, Diecast Devon [4]. Each Corgi die-cast model has a unique model ID. Professional online die-cast model shop Diecast Devon provides search function inputting the model ID as a key word. Virtually, CorgiPrice uses Diecast Devon search function as a Diecast Devon "API", though, this time, the input fields are explicit in the URL attribute of the HttpWebRequest object. CorgiPrice firstly sends request to the Diecast Devon search web page, then parses the item’s web page link from the search result. After that, CorgiPrice sends another request to link to the item’s web page on Diecast Devon, and then parses the item’s detail information by converting the response into a string object.

[Source Code Snippets, part of GetModelContent() ]

#region connect to www.diecastdevon.co.uk
// 1. use Diecast Devon Search page:
StringBuilder modelSearchSB = new StringBuilder();
byte[] buf = new byte[10000];
HttpWebRequest modelSearchRequest = (HttpWebRequest)WebRequest.Create("http://www.diecastdevon.co.uk/cgi-bin/ss000002.pl?SS=" + modelID + "&PR=-1&TB=A&SHOP=");
HttpWebResponse modelSearchResponse = (HttpWebResponse)modelSearchRequest.GetResponse();
#endregion
#region get search result, as a string
// get HTML search result content
Stream modelSearchStream = modelSearchResponse.GetResponseStream();
string modelSearchTempString = null;
int modelSearchCount = 0;
do
{
    // fill the buffer with data
    modelSearchCount = modelSearchStream.Read(buf, 0, buf.Length);
    // make sure we read some data
    if (modelSearchCount != 0)
    {
        // translate from bytes to ASCII text
        modelSearchTempString = Encoding.UTF8.GetString(buf, 0, modelSearchCount);
        // continue building the string
        modelSearchSB.Append(modelSearchTempString);
        }
    }
while (modelSearchCount > 0); // any more data to read?
string searchContent = modelSearchSB.ToString();
#endregion

XML Document Programming

The input fields of eBay APIs can be in XML format. Different call methods have different input filed definitions. The XML nodes indicate the input parameters. For an example, node <Query> specifies the query key words. Refer to eBay API reference pages [5] for the full input fields definitions of the call method GetSearchResults. CorgiPrice specifies node <eBayAuthToken>, <Query> and <IncludeSellers> as input.

[Input Fields of call method GetSearchResult]

<?xml version="1.0" encoding="utf-8" ?>
<GetSearchResultsRequest xmlns="urn:ebay:apis:eBLBaseComponents">
 <RequesterCredentials>
  <eBayAuthToken>YOURAUTHTOKEN</eBayAuthToken>
 </RequesterCredentials>
 <Query>corgi</Query>
 <UserIdFilter>
  <IncludeSellers>SELLERID</IncludeSellers>
 </UserIdFilter>
</GetSearchResultsRequest>

CorgiPrice uses System.XML assembly to generate the above XML document. The following source codes new a XML document, generate the XML declaration (<?xml version="1.0" encoding="utf-8" ?>), add a root node and its namespace (xmlns="urn:ebay:apis:eBLBaseComponents"), append child nodes, namespaces, and their inner texts, and convert the XML contents into a byte array for the HttpWebRequest object.

[Source Code Snippets, part of CallMethodInputXML()]

//Load the XML Document to Use for this Request
XmlDocument xmlDoc = new XmlDocument();
// Write down the XML declaration
XmlDeclaration xmlDeclaration = xmlDoc.CreateXmlDeclaration("1.0", "utf-8", null);
// Create the root element
XmlElement rootNode = xmlDoc.CreateElement("GetSearchResultsRequest", "urn:ebay:apis:eBLBaseComponents");
xmlDoc.InsertBefore(xmlDeclaration, xmlDoc.DocumentElement);
xmlDoc.AppendChild(rootNode);
// add <RequesterCredentials> node
XmlElement requesterCredentialsNode = xmlDoc.CreateElement("RequesterCredentials", "urn:ebay:apis:eBLBaseComponents");
rootNode.AppendChild(requesterCredentialsNode);
            
//      add <eBayAuthToken> node
XmlElement eBayAuthTokenNode = xmlDoc.CreateElement("eBayAuthToken", "urn:ebay:apis:eBLBaseComponents");
XmlText eBayAuthTokenText = xmlDoc.CreateTextNode(input.eBayAuthToken);
requesterCredentialsNode.AppendChild(eBayAuthTokenNode);
eBayAuthTokenNode.AppendChild(eBayAuthTokenText);
            
// add <Query> node
XmlElement queryNode = xmlDoc.CreateElement("Query", "urn:ebay:apis:eBLBaseComponents");
XmlText queryText = xmlDoc.CreateTextNode(input.query);
rootNode.AppendChild(queryNode);
queryNode.AppendChild(queryText);
if (input.includeSellers != "")
{
    // add <UserIdFilter> node
    XmlElement userIdFilterNode = xmlDoc.CreateElement("UserIdFilter", "urn:ebay:apis:eBLBaseComponents");
    rootNode.AppendChild(userIdFilterNode);
    //      add <IncludeSellers> node
    XmlElement includeSellersNode = xmlDoc.CreateElement("IncludeSellers", "urn:ebay:apis:eBLBaseComponents");
    XmlText includeSellersText = xmlDoc.CreateTextNode(input.includeSellers);
    userIdFilterNode.AppendChild(includeSellersNode);
    includeSellersNode.AppendChild(includeSellersText);
}
//Get XML into a string for use in encoding
string xmlText = xmlDoc.InnerXml;
//Put the data into a UTF8 encoded  byte array
UTF8Encoding encoding = new UTF8Encoding();
int dataLen = encoding.GetByteCount(xmlText);
byte[] utf8Bytes = new byte[dataLen];
Encoding.UTF8.GetBytes(xmlText, 0, xmlText.Length, utf8Bytes, 0);

CorgiPrice treats the output field (response) of the eBay API as an XML document as well. It extracts the content of a WebResponse object into an XML document by System.IO assembly.

[Source Code Snippets, part of GetUserListByTradingWebService()]

Stream stream = null;
//Get response into stream
WebResponse resp = request.GetResponse();
stream = resp.GetResponseStream();
// Get Response into XML
StreamReader streamReader = new StreamReader(stream);
XmlDocument xmlDoc = new XmlDocument();
xmlDoc.LoadXml(streamReader.ReadToEnd());
streamReader.Close();
stream.Close();

The following is an example of the node <Item> of the output XML document, which contains most of the interesting information about an item.

[Output XML document of call method GetSearchResults]

<ItemID xmlns="urn:ebay:apis:eBLBaseComponents">330152386754</ItemID>
<ListingDetails xmlns="urn:ebay:apis:eBLBaseComponents">
 <StartTime>2007-08-07T18:00:00.000Z</StartTime>
 <EndTime>2007-08-14T18:00:00.000Z</EndTime>
 <ViewItemURL>http://cgi.ebay.co.uk/CORGI-OOC-OM41002-AEC-4Q4-LONDON-PASSENGER-MIB_W0QQitemZ330152386754QQihZ014QQcategoryZ56314QQssPageNameZWDVWQQrdZ1QQcmdZViewItem</ViewItemURL>
 <ViewItemURLForNaturalSearch>http://cgi.ebay.co.uk/CORGI-OOC-OM41002-AEC-4Q4-LONDON-PASSENGER-MIB_W0QQitemZ330152386754QQcategoryZ56314QQcmdZViewItem </ViewItemURLForNaturalSearch>
</ListingDetails>
<SellingStatus xmlns="urn:ebay:apis:eBLBaseComponents">
 <BidCount>0</BidCount>
 <CurrentPrice currencyID="GBP">4.99</CurrentPrice>
</SellingStatus>
<Site xmlns="urn:ebay:apis:eBLBaseComponents">UK</Site>
<Title xmlns="urn:ebay:apis:eBLBaseComponents">CORGI OOC OM41002 AEC 4Q4 LONDON PASSENGER, MIB!</Title>
<Currency xmlns="urn:ebay:apis:eBLBaseComponents">GBP</Currency>
<ListingType xmlns="urn:ebay:apis:eBLBaseComponents">Chinese</ListingType>
<GiftIcon xmlns="urn:ebay:apis:eBLBaseComponents">0</GiftIcon>
<SiteHostedPicture xmlns="urn:ebay:apis:eBLBaseComponents">
 <GalleryType>Gallery</GalleryType>
</SiteHostedPicture>
<VendorHostedPicture xmlns="urn:ebay:apis:eBLBaseComponents">
 <GalleryURL>http://thumbs.ebay.com/pict/330152386754.jpg</GalleryURL>
 <GalleryType>Gallery</GalleryType>
</VendorHostedPicture>
<SubTitle xmlns="urn:ebay:apis:eBLBaseComponents"></SubTitle>
<PaymentMethods xmlns="urn:ebay:apis:eBLBaseComponents">PayPal</PaymentMethods>
<Country xmlns="urn:ebay:apis:eBLBaseComponents">GB</Country>
<BuyerProtection xmlns="urn:ebay:apis:eBLBaseComponents">ItemEligible</BuyerProtection>
<PostalCode xmlns="urn:ebay:apis:eBLBaseComponents">BD176JX</PostalCode>
<ShippingDetails xmlns="urn:ebay:apis:eBLBaseComponents">
 <ShippingType>Flat</ShippingType>
 <DefaultShippingCost currencyID="GBP">2.6</DefaultShippingCost>
</ShippingDetails>
<SearchDetails xmlns="urn:ebay:apis:eBLBaseComponents">
 <BuyItNowEnabled>false</BuyItNowEnabled>
</SearchDetails>
<ListingDuration xmlns="urn:ebay:apis:eBLBaseComponents">Days_7</ListingDuration>

CorgiPrice locates root node of the output XML document, then search for every <Item> nodes, extracting the details into an EBayGetSearchResultsNode object. The following source code snippets show how to access an XML node and extract its content (inner text or attribute) while knowing the XML document structure. Refer to eBay API reference pages [5] for the full output field definition of the call method GetSearchResults. Note that, the node definitions are fixed but not all the nodes would appear in the output XML document. As a result, the source codes include many node existing validations.

[Source Code Snippets, part of GetGetSearchResultsItem()]

node = new EBayGetSearchResultsNode();
node.itemID = n["ItemID"].InnerText;
node.startTime = DateTime.Parse(n["ListingDetails"]["StartTime"].InnerText);
node.endTime = DateTime.Parse(n["ListingDetails"]["EndTime"].InnerText);
node.itemURL = n["ListingDetails"]["ViewItemURL"].InnerText;
node.itemSearchURL = n["ListingDetails"]["ViewItemURLForNaturalSearch"].InnerText;
if (n["SellingStatus"]["BidCount"] != null)
    node.bidCount = Convert.ToInt16(n["SellingStatus"]["BidCount"].InnerText);
node.currentPrice = Convert.ToDouble(n["SellingStatus"]["CurrentPrice"].InnerText);
node.currentPriceCurrencyID = n["SellingStatus"]["CurrentPrice"].GetAttribute("currencyID");
node.site = n["Site"].InnerText;
node.title = n["Title"].InnerText;
node.currency = n["Currency"].InnerText;
node.listingType = n["ListingType"].InnerText;
node.giftIcon = n["GiftIcon"].InnerText;
if (n["SubTitle"] != null)
    node.subTitle = n["SubTitle"].InnerText;
if (n["PaymentMethods"] != null)
    node.paymentMethods = n["PaymentMethods"].InnerText;
node.country = n["Country"].InnerText;
if (n["BuyerProtection"] != null)
    node.buyerProtection = n["BuyerProtection"].InnerText;
if (n["PostalCode"] != null)
    node.postalCode = n["PostalCode"].InnerText;
node.shippingType = n["ShippingDetails"]["ShippingType"].InnerText;
if (n["ShippingDetails"]["DefaultShippingCost"] != null)
{
    node.defaultShippingCost = Convert.ToDouble(n["ShippingDetails"]["DefaultShippingCost"].InnerText);
    node.defaultShippingCostCurrencyID = n["ShippingDetails"]["DefaultShippingCost"].GetAttribute("currencyID");
}
if (n["SearchDetails"] != null)
    if (n["SearchDetails"]["BuyItNowEnabled"] != null)
        node.buyItNowEnabled = Convert.ToBoolean(n["SearchDetails"]["BuyItNowEnabled"].InnerText);
if (n["PictureDetails"] != null)
{
    if (n["PictureDetails"]["GalleryType"] != null)
    {
        node.galleryType = n["PictureDetails"]["GalleryType"].InnerText;
    }
}
else if (n["SiteHostedPicture"] != null)
{
    if (n["SiteHostedPicture"]["GalleryType"] != null)
    {
        node.galleryType = n["SiteHostedPicture"]["GalleryType"].InnerText;
    }
}
if (n["PictureDetails"] != null)
{
    if (n["PictureDetails"]["GalleryURL"] != null)
    {
        node.galleryURL = n["PictureDetails"]["GalleryURL"].InnerText;
    }
}
else if (n["VendorHostedPicture"] != null)
{
    if (n["VendorHostedPicture"]["GalleryURL"] != null)
    {
        node.galleryURL = n["VendorHostedPicture"]["GalleryURL"].InnerText;
    }
}
node.listingDuration = n["ListingDuration"].InnerText;

The content of the WebResponse object from Diecast Devon is a HTML webpage. The content is converted to a string object. The item details are then extracted by basic string matching methods. Refer to the source codes for details.

Multi-thread Programming

CorgiPrice’s workflow firstly gets item list from eBay, then searches the reference price of each item from Diecast Devon. There are sometimes hundreds of items on the watching list and all of them approaching the bidding end. Moreover, bidding is a real time task. It requires information updated frequently. As a result, CorgiPrice performances searching reference prices as a batch work on a new thread, starting from the item with the least bidding time left, and updating the reference price as soon as retrieving one from Diecast Devon.

CorgiPrice uses System.Thread assembly to develop a basic but safe multi-thread task. The new thread is in charge of searching the reference prices and updating the content of a ListView control, which belongs to its creation thread, the main thread. Windows form uses the Single-Threaded Apartment (STA) model which does not allow functions of the other thread to call its controls. However, the call from the other threads to a form’s control can be marshaled to its creation thread by methods such as Invoke(), which makes a synchronous call, and BeginInvoke(), which makes an asynchronous call. For an instance, MainForm Class defines a delegate to the method updating its ListView control. The reference price searching thread updates the ListView control by BeginInvoke the above delegate. Refer to MSDN .Net Framework Developer’s Guide [6] for details of multi-threaded Windows forms control programming.

[Source Code Snippets, part of MainForm.cs]

private delegate void UpdateListViewDelegate(int index, List<ItemNode> itemNodeList, ListView listView);
private UpdateListViewDelegate _updateListVieDelegate;
private Thread _referenceThread;
public MainForm()
{
    _updateListVieDelegate = new UpdateListViewDelegate(UpdateListView);
} 
private void OnStartGetReferencePrice(object sender, EventArgs e)
{
    _referenceThread = new Thread(new ThreadStart(this.UpdateReferencePrice));
    _referenceThread.Start();
}
/// <summary>
/// thread to update reference price
/// </summary>
private void UpdateReferencePrice()
{
    int itemCount = _itemNodeList.Count;
    for (int i = 0; i < itemCount; i++)
    {
        // get reference price
        GetReferencePrice(i, _itemNodeList);
        // get image
        GetImageInfo(i, _itemNodeList);
        // update list view
        IAsyncResult r2 = BeginInvoke(_updateListVieDelegate, new object[] { i, _itemNodeList, _listViewItems });
    }
} // UpdateReferencePrice()
/// <summary>
/// update list view
/// </summary>
/// <param name="index"></param>
/// <param name="itemNodeList"></param>
/// <param name="listView"></param>
private void UpdateListView(int index, List<ItemNode> itemNodeList, ListView listView)
{
    if ((index < 0) || (index >= itemNodeList.Count))
        throw new ApplicationException("MainForm::UpdateListView(), Index out of range.");
    ItemNode itemNode = (ItemNode)itemNodeList[index];
    ListViewItem listViewItem = listView.Items[index];
    if (itemNode.referenceNode != null)
    {
        double eBayPrice = itemNode.ebayNode.currentPrice;
        double referencePrice = itemNode.referenceNode.price;
        double advancedPrice = 0.0;
        if (referencePrice != 0)
            advancedPrice = referencePrice - eBayPrice;
        listViewItem.SubItems[2].Text = referencePrice.ToString();
        listViewItem.SubItems[3].Text = advancedPrice.ToString();
        if (advancedPrice > 20)
            listViewItem.BackColor = Color.Pink;
        listView.Focus();
    }
} // UpdateListView()

Conclusion and Future Work

CorgiPrice is a specific program, retrieving bidding items information from eBay, searching for the reference prices from another online shop, for the sake of assisting bidding.

To use the program, input an eBay Corgi die-cast model seller’s ID (for an example, andrewclarkmodels2 is an eBay power seller, who is a very serious Corgi die-cast model seller) to get his/her selling list or set it blank for retrieving all Corgi models on the bidding list. Item’s title, current bidding price, bid counts, end time and time left are listed in a row of a ListView control on the screen. The background thread automatically starts searching the reference prices in terms of the Corgi model ID appearing in the item’s title. Should Diecast Devon’s database have no such model or item’s title contains no match of a Corgi model ID, searching thread returns reference price as zero.

Figure 1 CorgiPrice User Interface

To use the source code, register to eBay developer program to obtain your own eBay development keys firstly. Then enter your own eBay development keys in method ConnectTradingWebService() and GetUserListByTradingWebService().

CorgiPrice is a preliminary prototype project, far from reaching a beta version. The obvious limitation includes:

  • CorgiPrice searches only Diecast Devon website.
  • CorgiPrice uses Corgi model IDs as key words for searching. However, a lot of eBay sellers are not as professional as andrewclarkmodels2 who lists clear information in item’s title. In these cases, CorgiPrice returns no reference price.

The only user of CorgiPrice thus far, my wife, is fairly entertained. However, she also has raised the other requests, such as

  • CorgiPrice should save the item list, especially for those biddings having ended. So that the user can check his/her harvests.
  • CorgiPrice should provide more options to get various lists from eBay, such as a user’s own watching list or winning list.

The most Interesting and challenging future works however, I think, mainly occur in the reference price searching task.

  • For an example, CorgiPrice could ultimately get the reference price directly from Google search results, using the whole item’s title as key words.
  • Moreover, CorgiPrice could also expand itself to assist bidding on the other die-cast model brands, or eventually the whole eBay items.

Reference

[1] eBay API, eBay developer program, http://developer.ebay.com/

[2] C# samples, http://developer.ebay.com/developercenter/windows/

[3] eBay quick start guide, http://developer.ebay.com/quickstartguide/

[4] Diecast Devon, http://www.diecastdevon.co.uk/

[5] eBay Trading Web Services ?Version 525 ?Input/Output Reference, GetSearchResults, http://developer.ebay.com/DevZone/XML/docs/Reference/eBay/io_GetSearchResults.html

[6] Multithreaded Windows Forms Control Sample, .Net Framework, Developer’s Guide, MSDN, http://msdn2.microsoft.com/en-us/library/3s8xdz5c(vs.71).aspx

History

1. 14.08.2007, first edition.

Read Full Post »

P2084312.JPG

Schmap Munich通知我,我在Flickr上放的两张照片被他们收用来介绍Munich的Manufactum商店。看来拍些犄角旮旯量大货全还是有胜出机会的 😛

这两张用的不是铮的专业机器,惭愧,好东西到了我手里出不来好东西。还是拿着小数码比划算了。

Technorati 标记: , , , ,

Read Full Post »

把戒指戴回去

厕所里有一本读者文摘的合订本,厕所读物。今天看到一则笑话:

二战期间,我发现我的结婚戒指在使用战壕铲时给弄坏了,于是我将戒指取下来挂在身份牌的链子上。从下士提升为上士后,我给妻子寄了一张我戴着新肩章的照片。我收到的回信中没有祝贺之词,只写了六个大字:“把戒指戴回去!”

老婆也是一样的,经常在照片上找我手上的戒指。不禁一笑。

Technorati 标记: , ,

Read Full Post »

小河马快15个月了。最近一个月的主题是走路。

开门见山的话,小河马现在已经名副其实的toddler了。(题外话,中文里面哪个词是说“蹒跚学步的小孩”?)

大概齐6月中迈的第一步吧,然后有走上三步的录像、有在公园练习走路的录像、也有在家里开始满处乱转的录像

最长的一次步行是在Roath Park,两周前了吧,一口气在甬路上走了百十来米。那天天气很好,久雨中少见的晴天,很多人都出门来赶上半天的太阳。公园里面很多人,而云震自己左晃右晃的占上了整个甬路,大人小孩阿猫阿狗鸡鸭雁鹅的都绕着他。

都说小孩刚会走路是要自己走个不停的。新鲜劲还没过去,摔跟头和坐屁墩的苦头还没记住,正是表现“机动性”的时候。

妈妈回来讲同事小孩的故事,和云震相仿年纪的小孩,会原地打转了。妈妈同事说这小孩已经“fully mobile”了。

云震还不会原地打转,但是满屋子溜达很随意,掉个头转个向驾轻就熟了。屋子还是小,云震晃几步就没的走了,折个头再往回晃。往往来来回回几个圈,双手举着,虽然走起来醉汉似的,但仍努力保持着平衡。手里随时攥着点东西,瓶盖或者小汽车。高兴了嘴里叨咕叨咕的,而或兴奋的叫上两声;不高兴了,哼哼唧唧的没头苍蝇一样四处转,似乎是找个合适的地方发上一通脾气。

爸爸以前说,等云震摔倒会自己不用扶桌子腿墙面就能爬起来了,这小孩就真的“fully mobile”了。

这些“技能”还真没人教,大概小孩对站立这件事越来越有信心了,自然而然就开始琢磨着站起来的方法了。

小河马已经掌握了两种站起来的方法,一种是跪起式。一种是撅起式。

撅起式,顾名思义,先直腿撅起屁股,双手撑地,腰上用力,把脑袋抬起来就站起来了。

跪起式,就是先单腿跪地,屈起的单腿用力,直接站起来。

我感觉跪起式比撅起式要费力,至少看着费力。虽然小河马是先琢磨出跪起式的,但现在越来越喜欢撅起式了,除非手里塞满了瓶盖和小汽车,没法撑地。

小河马走起来步子很大,老话说“不会走就要跑”就是这样的小孩。如此“奔”上几步,重心越来越在身子前面,摔个马趴避免不了,姥姥就心疼的紧着说:步子小点,步子小点。

步子大,更显出家里地方小了。外面地方大,可小河马玩上两次就不走了,因为外面摔的疼。

眼看着一个整天捧在手上的小东西满地跑了,想着小河马长大了。我想,眼看着小孩长大的父母都类似感觉吧,小孩长得很大了。可这里要说的是云震还是经常“暴露”出自己还是小孩。说“暴露”是开玩笑,但真的是这样的心情,往往是看着忙忙叨叨跑来跑去的小河马心里很满足的样子,突然发现:哦,原来这还是这么小的一个小东西呢。

小河马暴露自己是小小孩的特点大概如下:

走路的时候举着双手保持平衡。而且,就算举着双手,手还举不过头的样子。小小孩这时候脑袋大,胳膊短,举双手还真的举不过头顶呢。虽然有时候能拎上个积木桶走上几步,但离打酱油还早着呢。

小河马从小穿的都是分身的衣服,小衣服小裤子有模有样。衣服是套头绒杉,内衬一个白色的T恤,裤子是深色小牛仔。俗话将人靠衣裳,这小孩看着像模像样呢。可是走着走着或者爬着爬着,就看裤子腰上露出了尿布的边,哦,这还是一个穿尿布的小小孩嘛。

纵观小河马的照片,特别是妈妈精选的一些照片,爸爸妈妈老觉得小河马很懂事的样子,从小如此。满月的照片就瞪上眼睛,撇上小嘴,琢磨什么似的。稍微总结,直立上身和脑袋的照片尤其显得小河马大,虽然满月时候的照片是姥姥用手在后面托起脑袋照的。现在就更懂事啦,会走路了,当上个“搬运工”没问题,还乐此不疲。不仅如此,见什么东西都新鲜,指来指去的,“啊咕”一下。这下全毁了,再明白,不会说话是硬伤啊。

Technorati 标记: , , , , ,

Read Full Post »

我在CodeProject上写了一篇文章,提供一个利用Hit-and-Miss变换分割图形成线段的算法以及C#的源代码。这是我的PHD课题的一部分,单独不够成一篇文章,所以当作分享源代码好了。原文排版配色更好,特别是显示源代码的部分。贴在这仅凑上一篇文章数吧……

原文如下:

Split a single-pixel-width connected line graph into line segments by the Hit-and-Miss transformation


An algorithm is proposed to split a single-pixel-width connected line graph into line segments by the Hit-and-Miss transformation (HMT). Firstly, junction points and free end points are detected by a set of HMTs. Then, line segments are traced between junctions and free ends. The algorithm has been implemented in C#.

1. Introduction

1.1 Line graph and line segments

A single-pixel-width connected line graph (Figure 1 (a)) can be obtained by thinning [1] (thinning algorithm is not in the source codes) a black-and-white silhouette (Figure 1 (b)). The line segments are the basic components of the graph. Therefore, it has attracted much interest to split the graph into line segments. Nevertheless, it is not an easy task as it sounds.

black-and-white line graph

(a) (b)

Figure 1 (a) Example silhouette (b) thinning result, i.e., the single-pixel-width connected line graph

1.2 Challenges

Before going to the Hit-and-Miss transformation, the following strategy sounds facilely. Since the graph is connected, we can start from any free end, trace along the line segments, save the line segment and start multi-trace when comes to a junction. Nevertheless, it is far more difficult and complex than thought to design comprehensive rules for detecting a junction, or starting multi- line segments tracing. It is because the graph is connected by an 8-connected relationship.

In lattice image morphological theory, there are two simple neighbour relationships of the contiguous pixels. Figure 2(a) depicts a 4-connected relationship, while Figure 2 (b) depicts an 8-connected relationship. (Note that line segments are in black and background is white. Colourful figures are for display and illustration purpose.)

4-neighbour 8-neighbour

(a) (b)

Figure 2 (a) Four blue pixels are 4-connected neighbours of the red pixel (b) Eight green pixels are 8-connected neighbours of the red pixel.

If the graph is connected by an 8-connected relationship, it is then not always the case that only the pixel having only two neighbours is the part of a line segment stem, or the pixel is a junction if it has more than two neighbours. Figure 3 (a) shows an L-shape line segment, of which the red pixels have three neighbours according 8-connected relationship. But they cannot be regarded as junctions. Figure 3 (b) shows a cross graph, which should be split into four line segments. Only the red pixel should be detected as a junction, even though the blue pixels also have more than two neighbours. Figure 3 (c) shows another scenario where the number of the neighbours again is not capable to correctly detect the line segment stem and junctions. Though it is possible to labour a set of comprehensive rules to handle the above scenarios, Hit-and-Miss transformation can easily detect free ends of the line segments and the junctions, by which it is then a piece of cake to split the graph into line segments.

L-shape cross-figure another-scinario

(a) (b) (c)

Figure 3 (a) L-shape line segment (b) cross-figure graph (c) another scinario

1.3 Hit-and-Miss transform

The Hit-and-Miss transform is a basic binary morphological operation, which is generally used to detect particular patterns in a black-and-white image. The template, a.k.a., kernel, which is a small matrix, defines the particular patterns, with 1 meaning foreground pixel, 0 meaning background pixel, and "don’t care" pixels. For an instance, Figure 4 (a) gives a T-junction template. The template slides on the input binary image pixel-wise, does AND operation for all the pixels inside template expect those "don’t care’s". The corresponding pixel in the output binary image is set as the outcome of the "binary convolution". "True" means the template is exactly matched. For more of Hit-and-Miss transformation, please refer to the articles of CVOnline.

2. Algorithm

2.1 Detect junctions

Triple junction is a basic junction type. Figure 4 (a), (b) and (c) give three type of triple junction templates. By rotating Figure 4 (a) and (b) clockwise 90, 180, and 270 degrees, there are four Type1 and Type2 triple junction templates, respectively. By rotating Figure 4 (c) clockwise 45, 90, 135, ? and 315 degrees, there are eight Type3 triple junction templates. Note that there is no "0" element in these templates, so the Hit-and-Miss transformation (HMT) is done by an AndTrue2D operation, illustrated in Section 3.1.

Type1-template Type2-template Type3-template

(a) (b) (c)

Figure 4 (a) Type1 triple junction (T-junction) template (b) Type2 triple junction template (c) Type 3 triple junction template. Red pixels indicate foreground pixels. White pixels indicate "don’t care" pixels.

To solve the scenario as shown in Figure 3 (b), one more type of templates (Type4 as shown in Figure 5) is designed to detect the blue pixels and reject them as junctions. Also, by rotating clockwise every 90 degrees, there are four Type4 removal templates.

Type4-template

Figure 5 Type4 removal template. Red pixels indicate foreground. White pixels indicate "don’t care’s".

The algorithm of detecting junctions is:

Algorithm 1: Detect Junctions

a) Apply HMT (AndTrue2D) for each Type1 templates.

b) Apply HMT (AndTrue2D) for each Type2 and Type3 templates

c) Apply HMT (AndTrue2D) for each Type4 templates

d) OR the outcomes of step a) and b)

e) XOR the outcome of step d) with the outcomes of step c)

Source Code Snippet: part of JunctionDetector.Apply()

List<bool[,]> junctionMatrixList = new List<bool[,]>(16);
// AndTrue operations with 4 Type1 kernels, T-junction  
for (int i = 0; i < 4; i ++)
    junctionMatrixList.Add(HitAndMissTransformation.AndTrue2D(srcBoolMatrix, (bool[,])_kernelType1List[i]));
// AndTrue operation with 4 Type2 kernels
for (int i = 0; i < 4; i ++)
    junctionMatrixList.Add(HitAndMissTransformation.AndTrue2D(srcBoolMatrix, (bool[,])_kernelType2List[i]));
// AndTrue operation with 8 Type3 kernels
for (int i = 0; i < 8; i++)
    junctionMatrixList.Add(HitAndMissTransformation.AndTrue2D(srcBoolMatrix, (bool[,])_kernelType3List[i]));
// detect type 2 junctions which locate neighbour to type 1 junctions, T-junction direction            
List<bool[,]> junctionType4RemovalMatrixList = new List<bool[,]>(4);
for (int i = 0; i < 4; i++)
{
    junctionType4RemovalMatrixList.Add(HitAndMissTransformation.AndTrue2D(srcBoolMatrix, (bool[,])_kernelType4RemovalList[i]));
}
// OR result from Type1, Type2, and Type3
bool[,] dstMatrix = (bool[,])junctionMatrixList[0];
bool temp;
for (int i = 1; i < 16; i++)
// for each junction output
{
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            temp = ((bool[,])junctionMatrixList[i])[x, y];
            dstMatrix[x, y] = dstMatrix[x, y] || temp;
        }
    }
}            
// remove Type4 removal 
for (int i = 0; i < 4; i++)
// for each junction type 2 output
{
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            temp = ((bool[,])junctionType4RemovalMatrixList[i])[x, y];
            if (temp)
                dstMatrix[x, y] = false;  // remove operation
        }
    }
}

2.2 Detect Free Ends

There are three types of free end templates, pole-shape (Figure 6 (a)), L-shape (Figure 6 (b)), and T-shape (Figure 6 (c)). By rotating clockwise every 45 degrees, there are eight pole-shape and L-shape templates, respectively. By rotating clockwise every 90 degrees, there are four T-shape templates. Note that there are "0" elements requiring background also matches. Therefore, HMT is done by an AndTrueFalse2D operation, illustrated in Section 3.2.

pole-shape-template L-shape-template T-shape-template

(a) (b) (c)

Figure 6 (a) Pole-shape free end template (b) L-shape free end template (c) T-shape free end template. Red pixels indicate foreground pixels. Blue pixels indicate background pixels.

The algorithm of detecting free ends is:

Algorithm 2: Detect Free Ends

a) Apply HMT (AndTrueFalse2D) for each pole-shape templates;

b) Apply HMT (AndTrueFalse2D) for each L-shape templates;

c) Apply HMT (AndTrueFalse2D) for each T-shape templates;

d) OR the outputs of step a), b) and c).

Source Code Snippets: part of FreeEndDetector.Apply()

// AndTrue operations with 16 kernels
List<bool[,]> dstMatrixList = new List<bool[,]>(20);
for (int i = 0; i < 8; i++)
    dstMatrixList.Add(HitAndMissTransformation.AndTrueFalse2D(srcBoolMatrix, (bool[,])_kernelType1List[i]));
for (int i = 0; i < 8; i++)
    dstMatrixList.Add(HitAndMissTransformation.AndTrueFalse2D(srcBoolMatrix, (bool[,])_kernelType2List[i]));
for (int i = 0; i < 4; i++)
    dstMatrixList.Add(HitAndMissTransformation.AndTrueFalse2D(srcBoolMatrix, (bool[,])_kernelType3List[i]));
// OR all dstMatrixs
bool[,] dstMatrix = (bool[,])dstMatrixList[0];
int height = dstMatrix.GetLength(1);
int width = dstMatrix.GetLength(0);
bool temp;
for (int i = 1; i < 20; i++)
// for each AndTrue output
{
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            temp = ((bool[,])dstMatrixList[i])[x, y];
            dstMatrix[x, y] = dstMatrix[x, y] || temp;
        }
    }
}

2.3 Trace Line Segments

Once junction points and free ends have been detected, it is much easier now to split the graph into line segments. Each line segment has two end points (free end or junction) and some stem points. We start tracing a line segment from an end point to another end point by the following algorithm:

Algorithm 3: Trace One Line Segment

a) Search current point C‘s 8-connected neighbours;

b) If there are more than one 8-connected neighbours,

b.1) Search C‘s 4-connected neighbour, N4. (In this case, there must be one and only one 4-connected neighbour);

b.2) If N4 is a junction point, close the current line segment tracing at N4, remove C from the source image (i.e., set C as false);

b.3) Otherwise, current line segment extends to C, remove C from the source image, set the current point C as N4.

c) Otherwise,

c.1) If the 8-connected neighbour, N8, is a junction point, close the current line segment tracing at N8, remove C from the source image;

c.2) If the N8 is a free end, close the current line segment tracing at N8, remove C and N8 from the source image;

c.3) Otherwise, current line segment extends to C, remove C from the source image, set the current point C as N8.

Note that, Algorithm 3 removes free ends and stem points from the source image to avoid re-visiting of them. But, the junctions are remained.

Source Code Snippet: part of LineSegmentSplitter.TraceSingleLineSegment()

while (true)
// trace a line segment
{
    // search 8 neighbours
    List<Point> eightNeighbourList = Search8Neighbours(dstBoolMatrix, currentPoint);
    if (eightNeighbourList.Count > 1)
    // more than one 8 neighbours
    {
        // search 4 neighbours
        List<Point> fourNeighbourList = Search4Neighbours(dstBoolMatrix, currentPoint);
        if (fourNeighbourList.Count > 1)
            throw new ApplicationException("LineSegmentSplitter::ApplyDoubleGraylevelImageFilter(), current point is not a junction point but detected more than one 4 neighbours.");
        Point fourNeighbour = (Point)fourNeighbourList[0];
        if (IsInTripleJunctionList(fourNeighbour, tripleJunctionList))
        // the four neighbour is a junction point
        // close line segment at the junction point
        // stop tracing
        {
            lineSegment.AddEndPoint(new Point(fourNeighbour.X, fourNeighbour.Y));
            break;
        }
        else if (!(IsInFreeEndList(fourNeighbour, freeEndList)))
        // the four neighbour is a line segment point
        // add four neighbour to line segment
        // set four neighbour the current point
        // remove four neighbour from dst matrix
        {
            lineSegment.AddPoint(new Point(fourNeighbour.X, fourNeighbour.Y));
            RemoveFromDstMatrix(ref dstBoolMatrix, fourNeighbour);
            currentPoint = fourNeighbour;
        }
    }
    else
    // only one neighbours
    {
        Point neighbour = (Point)eightNeighbourList[0];
        if (IsInFreeEndList(neighbour, freeEndList))
        // next neighbour is an end point
        // close line segment at next neighbour
        // remove the end point from end point list
        // remove the end point from dstMatrix
        // stop tracing
        {
            lineSegment.AddEndPoint(new Point(neighbour.X, neighbour.Y));
            freeEndList.Remove(neighbour);
            RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
            break;
        }
        else if (IsInTripleJunctionList(neighbour, tripleJunctionList))
        // next neighbour is a junction point
        // close line segment at next neighbour                        
        // stop tracing
        {
            lineSegment.AddEndPoint(new Point(neighbour.X, neighbour.Y));
            break;
        }
        else
        // next neighbour is a line segment point
        // add neighbour to line segment
        // remove neighbour from dstMatrix
        // set neighbour as current point
        {
            lineSegment.AddPoint(new Point(neighbour.X, neighbour.Y));
            RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
            currentPoint = neighbour;
        }
    }
};  // while(true)

The following algorithm uses Algorithm 1, 2, and 3 to split the graph into line segments:

Algorithm 4: Split Graph into Line Segments

a) Apply Algorithm 1 to obtain junction points list;

b) Apply Algorithm 3 to obtain free end points list;

c) Start from each free end points, apply Algorithm 3 to trace line segments;

d) Start from each junction points’ 4-connected neighbours, apply Algorithm 3 to trace line segments;

e) Start from each junction point’s 8-connected neighbours, apply Algorithm 3 to trace line segments;

f) Remove those isolated junction points or connect the contiguous junction points.

Source Code Snippet: part of LineSegmentSplitter.Apply()

// start tracing line segment from end points
while (_freeEndList.Count > 0)
// for each end point
{
    Point currentPoint = (Point)_freeEndList[0];
    _freeEndList.RemoveAt(0);   // remove end point from end point list  
    LineSegment lineSegment = new LineSegment();
    // add current point in line segment as "end point"
    lineSegment.AddEndPoint(new Point(currentPoint.X, currentPoint.Y));
    // remove current point from dstMatrix
    RemoveFromDstMatrix(ref dstBoolMatrix, currentPoint);
    // trace single line segment
    TraceSingleLineSegment(ref lineSegment, ref currentPoint, ref dstBoolMatrix, ref _freeEndList, ref _tripleJunctionList);
    _lineSegmentList.Add(lineSegment);
}; // while(_freeEndList.Count > 0)
// start tracing line segments from junction points
// firstly, trace only 4-neighbours of all the junction points
foreach (Point junctionPoint in _tripleJunctionList)
{
    RemoveFromDstMatrix(ref dstBoolMatrix, junctionPoint);
    List<Point> fourNeighbourList = Search4Neighbours(dstBoolMatrix, junctionPoint);
    while (fourNeighbourList.Count > 0)
    {
        Point neighbour = fourNeighbourList[0];
        // remove the other neighbours from dst matrix
        for (int i = 1; i < fourNeighbourList.Count; i++)
            RemoveFromDstMatrix(ref dstBoolMatrix, (Point)fourNeighbourList[i]);
        LineSegment lineSegment = new LineSegment();
        lineSegment.AddEndPoint(new Point(junctionPoint.X, junctionPoint.Y));
        Point currentPoint = neighbour;
        // current point could be a junction point or a line segment point
        if (!IsInTripleJunctionList(currentPoint, _tripleJunctionList))
        // current is a line segment point
        {
            lineSegment.AddPoint(new Point(currentPoint.X, currentPoint.Y));
            RemoveFromDstMatrix(ref dstBoolMatrix, currentPoint);                        
            TraceSingleLineSegment(ref lineSegment, ref currentPoint, ref dstBoolMatrix, ref _freeEndList, ref _tripleJunctionList);
            _lineSegmentList.Add(lineSegment);
        }
        // add the other neighbours to dst matrix
        for (int i = 1; i < fourNeighbourList.Count; i++)
            AddToDstMatrix(ref dstBoolMatrix, (Point)fourNeighbourList[i]);
        fourNeighbourList.RemoveAt(0);
    } // while (fourNeighbourList.Count > 0)
    AddToDstMatrix(ref dstBoolMatrix, junctionPoint);
} // foreach _tripleJunctionList
// secondly, trace only 4-diagonal-neighbours of all the junction points
foreach (Point junctionPoint in _tripleJunctionList)
{
    RemoveFromDstMatrix(ref dstBoolMatrix, junctionPoint);
    List<Point> fourDiagonalNeighbourList = SearchDiagonal4Neighbours(dstBoolMatrix, junctionPoint);
    while (fourDiagonalNeighbourList.Count > 0)
    {
        Point neighbour = (Point)fourDiagonalNeighbourList[0];
        // remove the other neighbours from the dst matrix
        for (int i = 1; i < fourDiagonalNeighbourList.Count; i++)
            RemoveFromDstMatrix(ref dstBoolMatrix, (Point)fourDiagonalNeighbourList[i]);
        LineSegment lineSegment = new LineSegment();
        lineSegment.AddEndPoint(new Point(junctionPoint.X, junctionPoint.Y));
        Point currentPoint = neighbour;
        // current point could be a junction point or a line segment point
        if (!IsInTripleJunctionList(currentPoint, _tripleJunctionList))
        // current is a line segment point
        {
            lineSegment.AddPoint(new Point(currentPoint.X, currentPoint.Y));
            RemoveFromDstMatrix(ref dstBoolMatrix, currentPoint);
            TraceSingleLineSegment(ref lineSegment, ref currentPoint, ref dstBoolMatrix, ref _freeEndList, ref _tripleJunctionList);
            _lineSegmentList.Add(lineSegment);
        }
        // add the other neighbours to the dst matrix
        for (int i = 1; i < fourDiagonalNeighbourList.Count; i++)
            AddToDstMatrix(ref dstBoolMatrix, (Point)fourDiagonalNeighbourList[i]);
        fourDiagonalNeighbourList.RemoveAt(0);
    } // while(fourDiagonalNeighbourList.Count > 0)
    AddToDstMatrix(ref dstBoolMatrix, junctionPoint);
}
// thirdly, connect the contiguous junction points  
foreach (Point junctionPoint in _tripleJunctionList)
{
    List<Point> neighbourList = Search8Neighbours(dstBoolMatrix, junctionPoint);
    if (neighbourList.Count == 0)
        RemoveFromDstMatrix(ref dstBoolMatrix, junctionPoint);
    else
    {
        foreach (Point endPoint in neighbourList)
        {
            LineSegment lineSegment = new LineSegment();
            lineSegment.AddEndPoint(new Point(junctionPoint.X, junctionPoint.Y));
            lineSegment.AddEndPoint(new Point(endPoint.X, endPoint.Y));
            _lineSegmentList.Add(lineSegment);
        }
        RemoveFromDstMatrix(ref dstBoolMatrix, junctionPoint);
    }
}

3. Hit-and-Miss Transform Source Codes

3.1 AndTrue2D

Source Code Snippet: part of HitAndMissTransformation.AndTrue2D()

bool[,] expandSrcBoolMatrix = BoundFillingBackgroundIntensityExpand(srcBoolMatrix, kernel);
// prepare dst bool matrix
int expandHeight = expandSrcBoolMatrix.GetLength(1);
int expandWidth = expandSrcBoolMatrix.GetLength(0);
bool[,] expandDstBoolMatrix = new bool[expandWidth, expandHeight];
int xStart = halfWk;
int xEnd = width + halfWk;
int yStart = halfHk;
int yEnd = height + halfHk;
for (int x = xStart; x < xEnd; x++)
{
    for (int y = yStart; y < yEnd; y++)
    {
        bool isHit = true;
        // inside kernel
        for (int kx = -1 * halfWk; kx <= halfWk; kx++)
        {
            for (int ky = -1 * halfHk; ky <= halfHk; ky++)
            {
                // kernel, expandSrcBoolMatrix, and expandDstBoolMatrix are bool[,]
                if (kernel[kx + halfWk, ky + halfHk])
                // kernel element is true
                {
                    if (!expandSrcBoolMatrix[x + kx, y + ky])
                    // image element is false
                    {
                        isHit = false;
                        break;
                    }
                }
            }
        }
        expandDstBoolMatrix[x, y] = isHit;
    }
}
bool[,] dstBoolMatrix = BoundFillingBackgroundIntensityShrink(expandDstBoolMatrix, kernel);

Note that, before apply "binary convolution", the source image is boundary expanded by filling the expanded part background values (False).

3.2 AndTrueFalse2D

Source Code Snippet: part of HitAndMissTransformation.AndTrueFalse2D():

bool[,] expandSrcBoolMatrix = BoundFillingBackgroundIntensityExpand(srcBoolMatrix, kernel);
// prepare dst bool matrix
int expandHeight = expandSrcBoolMatrix.GetLength(1);
int expandWidth = expandSrcBoolMatrix.GetLength(0);
bool[,] expandDstBoolMatrix = new bool[expandWidth, expandHeight];
int xStart = halfWk;
int xEnd = width + halfWk;
int yStart = halfHk;
int yEnd = height + halfHk;
for (int x = xStart; x < xEnd; x++)
{
    for (int y = yStart; y < yEnd; y++)
    {
        bool isHit = true;
        // inside kernel
        for (int kx = -1 * halfWk; kx <= halfWk; kx++)
        {
            for (int ky = -1 * halfHk; ky <= halfHk; ky++)
            {
                // kernel is a bool[,]
                // expandSrcBoolMatrix, and expandDstBoolMatrix are bool[,]
                if ((kernel[kx + halfWk, ky + halfHk] && !expandSrcBoolMatrix[x + kx, y + ky])
                    || (!kernel[kx + halfWk, ky + halfHk] && expandSrcBoolMatrix[x + kx, y + ky]))
                {
                    isHit = false;
                    break;
                }
            }
        }
        expandDstBoolMatrix[x, y] = isHit;
    }
}
bool[,] dstBoolMatrix = BoundFillingBackgroundIntensityShrink(expandDstBoolMatrix, kernel);

4. Results and Conclusion

It turns out much easier to develop Algorithm 1 to Algorithm 4 and implement them by C# to split a single-pixel-width connected graph into line segments. Figure 7 shows the split line segments. Line segment ends are in red while stem points are in blue. Algorithm 1 detects junctions, covering every scenario shown in Figure 3 and the ones not shown. Algorithm 2 detects free ends. Algorithm 4 accomplishes splitting the graph into line segments.

line segments

Figure 7 Line segments image

Reference

[1] Peter I Rockett, An Improved Rotation-Invariant Thinning Algorithm. IEEE Trans. Pattern Anal. Mach. Intell. 27(10): 1671-1674 (2005)

History

1. 01.08.2007, first version.

Read Full Post »